//
// Created by liushuai on 2020/3/18.
//
#include "Node.h"
int linklistLength(Node* head){
    int length = 0;
    Node* current = head;
    while (current){
        length++;
        current = current->next;
    }
    return length;
}
Node* reverseLinkList(Node* head){
    Node* tail= nullptr;
    Node* currentNode=head;
    Node* preNode= nullptr;
    while (currentNode){
        Node* nextNode = currentNode->next;
        if(!nextNode)
            tail=currentNode;
        currentNode->next=preNode;
        preNode=currentNode;
        currentNode=nextNode;
    }
    return tail;

}
bool isPalindrome(Node* head){
    if(!head)
        return true;
    Node* current = head;
    Node* fast = head;
    Node* slow = head;
    int length=linklistLength(head);
    int middle = length/2;
    for(int i=0;i<middle;i++){
        if(fast){
            fast=fast->next;
        }
    }
    Node* palindromeNode = reverseLinkList(fast);
    while (slow){
        if(palindromeNode){
            if(slow->value==palindromeNode->value){
                slow=slow->next;
                palindromeNode->next;
            }else{
                return false;
            }
        }
    }
    return true;
}

